package mid.class1;

import common.ArrayUtils;

/**
 * KMP算法解决的问题
 * str1 = "ABC1234de"
 * str2 = "1234"
 * 求 str1 是不是 str2 的子串
 * <p>
 * https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
 * 找出字符串中第一个匹配项的下标
 */
public class Code01_KMP {

    public static void main(String[] args) {
        String str1 = "aaabacbaabababaa";
        String str2 = "babaa";
        int index = KMPSearch(str1.toCharArray(), str2.toCharArray());
        ArrayUtils.printArr(index);

    }

   // KMP算法匹配
    public static int KMPSearch(char[] s1, char[] s2) {
        int n = s1.length, x = 0;
        int m = s2.length, y = 0;
        int[] next = nextArray(s2, m);
        ArrayUtils.printArr(next);

        /**
         * 当循环结束时，可能 x 越界，也可能时 y 越界
         */
        while (x < n && y < m) {
            if (s1[x] == s2[y]) {
                x++;
                y++;
            } else if (y == 0) { // 如果模式指针y回到开头
                x++;  // 文本指针后移，跳过当前字符
            } else { // 如果y != 0，跳到下一个可能的匹配位置
                y = next[y];
            }
        }
        /**
         * 1.如果 x>=n,说明 x 越界， 此时 y != m ，则返回 -1,没有查到该字符串
         * 2.如果 y>=m,则说明 y 越界，此时 y++刚好等于m，x-y 就是匹配的起始位置
         */
        return y == m ? x - y : -1;

    }

    /**
     * 计算next字符串
     * *[ a b a a b a a b a b a b a b b a]
     * *[-1 0 0 1 1 2 3 4 5 6 2 3 2 3 2 0]
     * *[ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
     * <p>
     * * a b a b c a b a b
     * *-1 0 0 1 2 0 1 2 3
     */

    /**
     * next 字符串
     * aabaas -1 0
     * next[0] = -1; 从字符串的第一个字符开始没有前缀和后缀相同
     * next[1] = 0; 从第二个字符开始，前缀和后缀长度为 0
     * i :是当前要求 next 数组值的位置
     * cn:表示当前需要与前一个字符比较的下标，即前缀的长度。
     */
    public static int[] nextArray(char[] s, int m) {
        if (m == 1) {
            return new int[]{0};
        }
        int[] next = new int[m];
        next[0] = -1;
        next[1] = 0;
        int i = 2, cn = 0; // i 从2开始
        // aabaaba
        while (i < m) {
            // 如果当前字符 s[i - 1] 与前缀中的字符 s[cn] 相等，说明可以扩展当前的前缀与后缀的匹配长度,
            if (s[cn] == s[i - 1]) {
                // next[i++] = ++cn，然后 i++，继续下一个字符的计算
                next[i++] = ++cn;
            } else if (cn > 0) { // cn > 0，说明已经有部分前缀和后缀匹配过，那么可以通过 cn = next[cn] 跳过不必要的字符，尝试找更小的前缀和后缀匹配长度

                // cn 表示当前已经匹配的前缀长度。 比如，cn=3 表示前 3 个字符已经匹配成功。

                // * 当匹配失败时，cn = next[cn] 表示回退到当前匹配前缀的最长相等前缀末尾，继续尝试匹配。
                // 这样做可以利用已经匹配的部分信息，避免从头开始匹配。
                cn = next[cn]; // 回退逻辑
            } else {
                // else：如果没有任何匹配，说明 next[i] 为 0，表示当前字符没有任何匹配的前缀和后缀。
                next[i++] = 0;
            }
        }
        return next;
    }

    /**
     * 匹配过程
     * a  b  a  b  a  a  b  a  b  a  b
     * <p>
     * 0  1  2  3  4  5  6  7  8  9  10
     * <p>
     * -1 0  0  1  2  3  1  2  3  4  5
     * <p>
     * s[cn] = s[i-1] cn = 0 i = 2
     * <p>
     * s[0] == s[1]   next[2] = 0 cn = 0 i++ = 3
     * <p>
     * s[0] == s[2]   next[3] = 1 cn = 1 i++ = 4
     * <p>
     * s[1] == s[3]   next[4] = 2 cn = 2 i++ = 5
     * <p>
     * s[2] == s[4]   next[5] = 3 cn = 3 i++ = 6
     * --
     * s[3] == s[5]   cn>0  cn = next[3]  cn = 1
     * <p>
     * s[1] == s[5]   cn>0  cn = next[1]  cn = 0
     * --
     * s[0] == s[5]   next[6] = 1 cn = 1 i++ = 7
     * <p>
     * s[1] == s[6]   next[7] = 2 cn = 2 i++ = 8
     * <p>
     * s[2] == s[7]   next[8] = 3 cn = 3 i++ = 9
     * <p>
     * s[3] == s[8]   next[9] = 4 cn = 4 i++ = 10
     * <p>
     * s[4] == s[9]   next[10]= 5 cn = 5 i++ = 11
     */
    public static void test() {

    }
}
